Dijkstra's algorithm evolves the concepts from BFS, upgrading its data structures to handle weighted graphs.
- Recall BFS uses a simple Queue (First-In, First-Out) to explore neighbors and a Visited Set to track visited nodes.
- Dijkstra's requires a more powerful structure: a Priority Queue (Min-Heap). This isn't FIFO; it always extracts the node with the smallest known distance, enforcing the greedy strategy.
- Instead of a boolean `visited` set, Dijkstra's uses a Distance Array ($d[v]$). This not only tracks visited nodes (any node with distance $<\infty$) but also stores the current best path cost to them.
- This upgrade is key: the Priority Queue ensures we always explore from the most promising frontier, while the Distance Array allows us to relax edges by comparing and updating path costs.
Key Data Structures Summary
| Data Structure | Purpose | Key Operation |
|---|---|---|
| Distance Array $d$ | Stores shortest distance so far to each node $v$. | $d[v] = new\_cost$ (Update) |
| Priority Queue $pq$ | Stores $(cost, vertex)$ pairs for unvisited nodes. | $pq.pop()$ (Get min-distance node) |